package 动态规划9月;
//统计小于等于n的1的个数
//public class Solution {
//    public static  int fun(int n){
//        int count=0;
//        for(int i=1;i<=n;++i){
//            int num=i;
//           while(num!=0){
//                if(num%10==1)
//                    count++;
//                num=num/10;
//            }
//        }
//        return  count;
//    }
//    public static void main(String[] args) {
//        System.out.println(fun(10));
//    }
//}


import java.util.*;

//24点游戏
public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 输入：
     从1-13个数中，有放回抽取的4个数
     输出：
     若这4个数可以通过运用加、减、乘、除和括号进行运算得出24，则返回true，否则返回false
     * @param input int整型一维数组 从1-13个数中，有放回抽取的4个数
     * @return bool布尔型
     */
    public boolean solution (int[] input) {
        // write code here
        List<Double> list=new ArrayList<>();
        for(int i:input){
            list.add((double)i);
            System.out.println(i);
        }
        return dfs(list);
    }

    private boolean dfs(List<Double> list) {
        if(list.size()==1){
            if(Math.abs(list.get(0)-24)<0.001){
                return true;
            }
            return false;
        }
        for (int i = 0; i < list.size(); i++) {
            for(int j=i+1;j<list.size();j++){
                for(double c:compute(list.get(i),list.get(j))){
                    List<Double> nextround=new ArrayList<>();
                    nextround.add(c);
                    for(int k=0;k<list.size();k++){
                        if(k==i||k==j){
                            continue;
                        }
                        nextround.add(list.get(k));
                    }
                    if(dfs(nextround))return true;
                }
            }

        }
        return false;
    }


    private List<Double> compute(double a, double b) {
        List<Double> list=Arrays.asList(a+b,a-b,b-a,a*b,a/b,b/a);
        return list;
    }

    public static void main(String[] args) {
        System.out.println(new Solution().solution(new int[]{2,4,6,12}));
    }

}